/*
 * @Author: Starfish_DL
 * @Date: 2020-10-09 17:51:52
 * @LastEditors: Starfish_DL
 * @LastEditTime: 2020-10-13 00:38:03
 * @CurrentVersion: 1.0
 * @Description: 
 */

#include<iostream>
#define MAXSIZE 64
using namespace std;

class box
{
public:
    int x;
    int y;
    int pre;
    box(int x,int y);
    box();
    ~box();
};

box::box(int x,int y)
{
    this->x=x;
    this->y=y;
}

box::box()
{
}

box::~box()
{
}

class iSqQueue
{
public:
    box boxSqQueue[MAXSIZE];
    int front;
    int rear;
    bool isEmpty();
    void enQueue(box e);
    box deQueue();
    iSqQueue();
    ~iSqQueue();
};

iSqQueue::iSqQueue()
{
    for (int i = 0; i < MAXSIZE; i++)
    {
        boxSqQueue[i]=box();
    }
    this->front=-1;
    this->rear=-1;
}

bool iSqQueue::isEmpty()
{
    return (this->front==this->rear);
}

void iSqQueue::enQueue(box e)
{
    this->rear++;
    this->boxSqQueue[this->rear]=e;
    return;
}

box iSqQueue::deQueue()
{
    if (this->isEmpty())
    {
        return box(0,0);
    }
    this->front++;
    return this->boxSqQueue[this->front];
}

iSqQueue::~iSqQueue()
{
}

int map[10][10]=
{
    {1,1,1,1,1,1,1,1,1,1}, //0
    {1,0,0,1,0,1,0,1,0,1}, //1
    {1,0,0,1,0,1,0,1,0,1}, //2
    {1,0,0,0,0,1,1,0,0,1}, //3
    {1,0,1,1,1,0,0,0,0,1}, //4
    {1,0,0,0,1,0,0,0,0,1}, //5
    {1,0,1,0,0,0,1,0,0,1}, //6
    {1,0,1,1,1,0,1,1,0,1}, //7
    {1,1,0,0,0,0,0,0,0,1}, //8
    {1,1,1,1,1,1,1,1,1,1}  //9
    //tag 地图的'1'表示墙,'0'表示地面,为了方便将四周设置为墙;
};

void mgPath(box begin,box end)
{
    iSqQueue mapSqQueue;
    mapSqQueue.enQueue(begin);
    map[begin.x][begin.y]=1;
    while (!mapSqQueue.isEmpty())
    {
        box temp=mapSqQueue.deQueue();
        if (temp.x==end.x && temp.y==end.y)
        {
            cout<<"Success!"<<endl;
            cout<<"("<<temp.x<<","<<temp.y<<")"<<endl;
            while (mapSqQueue.rear!=0)
            {
                mapSqQueue.rear=temp.pre;
                temp=mapSqQueue.boxSqQueue[mapSqQueue.rear];
                cout<<"("<<temp.x<<","<<temp.y<<")"<<endl;
            }
            return;
        }
        box boxtemp[4]=
        {
            boxtemp[0]=box(temp.x,temp.y+1),
            boxtemp[1]=box(temp.x+1,temp.y),
            boxtemp[2]=box(temp.x,temp.y-1),
            boxtemp[3]=box(temp.x-1,temp.y)
        };
        for (int i = 0; i < 3; i++)
        {
            if (map[boxtemp[i].x][boxtemp[i].y]!=1)
            {
                mapSqQueue.enQueue(boxtemp[i]);
                mapSqQueue.boxSqQueue[mapSqQueue.rear].pre=mapSqQueue.front;
                map[boxtemp[i].x][boxtemp[i].y]=1;
            }
        }    
    }
    cout<<"Failure!"<<endl;
    return;
}

int main()
{
    box a(1,1);
    box b(8,8);
    mgPath(a,b);
    return 0;
}